﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;
using System.Windows.Threading;
using System.Threading;

namespace TravelingSalesmanEvolution
{
    /// <summary>
    /// Interaction logic for MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        graph graph;
        Random rnd;

        double alfa = 0.1;
        double beta = 100;
        double lower = 0.1;

        bool dontVisitAgain = false;
        bool biDirectional = true;

        int iterations = 100;
        int ants = 100;

        int maxPoi = 100;
        int samples = 1000;

        int maxCharacters = 20000;
        bool doThreads = true;
        bool calculateWeights = false;
        bool allOutput = true;
        bool output = true;

        bool work = false;

        public delegate void AntsDelegate();
        public delegate void EvoDelegate();

        public MainWindow()
        {
            InitializeComponent();
            rnd = new Random();
        }

        // load data from text file (.txt)
        private void loadTxt_Click(object sender, RoutedEventArgs e)
        {

            loadTxtMethod();

            //String[] lines;

            //Microsoft.Win32.OpenFileDialog openDialog = new Microsoft.Win32.OpenFileDialog();
            //Nullable<bool> result = openDialog.ShowDialog();
            //if (result == true)
            //{
            //    lines = System.IO.File.ReadAllLines(openDialog.FileName);
            //    graph = new graph(lines.Count());

            //    foreach (String l in lines)
            //    {
            //        String[] split = l.Split(' ');
            //        int c = 0, t = 0;
            //        int.TryParse(split[1], out c);
            //        int.TryParse(split[2], out t);
            //        graph.addTuple(split[0], c, t);
            //    }

            //    int i = 0;
            //    foreach (String l in lines)
            //    {
            //        String[] split = l.Split(' ');
            //        graph.tmp = 0;
            //        for (int j = 0; j < graph.poi[i].Item3.Count(); j++)
            //        {
            //            int d = 0, c = 0;
            //            int.TryParse(split[3 + graph.tmp], out d);
            //            int.TryParse(split[4 + graph.tmp], out c);
            //            graph.addRoad(i, d, c);
            //        }
            //        i++;
            //    }

            //    randomize.IsEnabled = true;

            




        }

        private void loadTxtMethod()
        {
            String[] lines;
            String[] lines2;

            Microsoft.Win32.OpenFileDialog openDialog = new Microsoft.Win32.OpenFileDialog();
            openDialog.DefaultExt = ".txt";
            openDialog.FileName = "cities.txt";
            Nullable<bool> result = openDialog.ShowDialog();
            if (result == true)
            {
                Microsoft.Win32.OpenFileDialog openDialog2 = new Microsoft.Win32.OpenFileDialog();
                openDialog2.DefaultExt = ".txt";
                openDialog2.FileName = "distances.txt";
                Nullable<bool> result2 = openDialog2.ShowDialog();
                if (result2 == true)
                {
                    lines = System.IO.File.ReadAllLines(openDialog.FileName);
                    lines2 = System.IO.File.ReadAllLines(openDialog2.FileName);

                    if (lines[lines.Count() - 1].Equals(String.Empty))
                        lines = lines.Take(lines.Count() - 1).ToArray();
                    if (lines2[lines2.Count() - 1].Equals(String.Empty))
                        lines2 = lines2.Take(lines2.Count() - 1).ToArray();

                    if (lines.Count() != lines2.Count())
                    {

                        return;
                    }

                    graph = new graph(lines.Count());

                    for (int i = 0; i < lines.Count(); i++)
                    {
                        String[] split = lines[i].Split(' ');
                        String[] split2 = lines2[i].Split(' ');
                        int c = 0, t = 0;
                        int.TryParse(split[2], out c);
                        if (split2[split2.Count()-1].Equals(String.Empty))
                            split2 = split2.Take(split2.Count() - 1).ToArray();
                        t = split2.Count() - 1;
                        if (t % 2 == 1)
                            return;
                        t = t / 2;
                        graph.tmp = i;
                        graph.addTuple(split[1], c, t);
                        graph.tmp = 0;
                        for (int j = 0; j < graph.poi[i].Item3.Count(); j++)
                        {
                            int d = 0, dc = 0;
                            int.TryParse(split2[1 + graph.tmp], out d);
                            int.TryParse(split2[2 + graph.tmp], out dc);
                            graph.addRoad(i, d, dc);
                        }
                    }

                    randomize.IsEnabled = true;
                }
            }
        }


        private void loadDefault_Click(object sender, RoutedEventArgs e)
        {
            String[] lines = {"1 5 4 2 28 4 12 6 11 7 19", "2 3 3 1 28 3 34 7 25", "3 2 2 2 34 4 35", "4 4 5 1 12 3 35 5 28 8 47 9 24", "5 2 3 4 28 6 15 9 38", "6 1 3 1 11 5 15 7 24", "7 2 3 1 19 2 25 6 24", "8 4 2 4 47 9 32", "9 3 3 4 24 5 38 8 32"};
            graph = new graph(lines.Count());

            foreach (String l in lines)
            {
                String[] split = l.Split(' ');
                int c = 0, t = 0;
                int.TryParse(split[1], out c);
                int.TryParse(split[2], out t);
                graph.addTuple(split[0], c, t);
            }

            int i = 0;
            foreach (String l in lines)
            {
                String[] split = l.Split(' ');
                graph.tmp = 0;
                for (int j = 0; j < graph.poi[i].Item3.Count(); j++)
                {
                    int d = 0, c = 0;
                    int.TryParse(split[3 + graph.tmp], out d);
                    int.TryParse(split[4 + graph.tmp], out c);
                    graph.addRoad(i, d, c);
                }
                i++;
            }

            randomize.IsEnabled = true;

        }

        double[][] pheromones;
        int i, max;
        List<road> roads;

        // generate starting population with ant algorithm
        private void mrowkowy_Click(object sender, RoutedEventArgs e)
        {
            max = 0;
            if (!int.TryParse(Cmax.Text, out max))
            {

                return;
            }

            work = true;
            stop.IsEnabled = true;

            debugPopulate.Text = "";
            mrowkowy.IsEnabled = false;
            randomize.IsEnabled = false;

            // pheromones of ants for every [point][road]
            
            pheromones = new double[graph.poi.Count()][];
            int hlp = 0;
            foreach (Tuple<String, int, Tuple<int, int>[]> t in graph.poi)
            {
                pheromones[hlp] = new double[t.Item3.Count()];
                hlp++;
            }
            for (int m1 = 0; m1 < graph.poi.Count(); m1++)
            {
                for (int m2 = 0; m2 < graph.poi[m1].Item3.Count(); m2++)
                {
                    pheromones[m1][m2] = 1;
                }
            }


            i = 0;
            // this much tries of ants
            if (doThreads)
                Dispatcher.BeginInvoke(
                        System.Windows.Threading.DispatcherPriority.SystemIdle,
                        new AntsDelegate(doAnts));
            else
                doAnts();

            //foreach (var d in roads)
            //{
            //    debugPopulate.Text += "Droga: " + mee + "; dlugosc: " + d.length + "; zysk: " + d.profit + "\n";
            //    foreach (var de in d.poi)
            //    {
            //        debugPopulate.Text += de+1 + " ";
            //    }
            //    debugPopulate.Text += "\n";
            //    mee++;
            //}


        }

        int bestSoFar = 0;
        int bestSoFarNo = 0;

        // random roads
        private void randomize_Click(object sender, RoutedEventArgs e)
        {
            


            max = 0;
            if (!int.TryParse(Cmax.Text, out max))
            {
                Cmax.Text = "100";
                max = 100;
            }

            if (!int.TryParse(Samples.Text, out samples))
            {
                Samples.Text = "1000";
                samples = 1000;
            }
            slider1.Maximum = samples;

            if (checkBoxShowOnlyBest.IsChecked == true)
            {
                allOutput = false;
            }
            else allOutput = true;

            if (checkBoxWeighted.IsChecked == true)
            {
                calculateWeights = true;
            }
            if (checkBoxOutput.IsChecked == true)
            {
                output = true;
            }
            else output = false;

            if (!int.TryParse(Mmax.Text, out maxPoi))
            {
                Mmax.Text = "100";
                maxPoi = 100;
            }


            bestSoFar = 0;
            work = true;
            stop.IsEnabled = true;

            roads = new List<road>();

            debugPopulate.Text = "";
            mrowkowy.IsEnabled = false;
            randomize.IsEnabled = false;

            i = 0;

            if (work)
                if (doThreads)
                    Dispatcher.BeginInvoke(
                        System.Windows.Threading.DispatcherPriority.SystemIdle,
                        new AntsDelegate(generateRandom));
                else
                    generateRandom();
            else
            {
                mrowkowy.IsEnabled = true;
                randomize.IsEnabled = true;
            }

        }


        private void generateRandom()
        {

            if (roads.Count < samples)
            {
                int pos = 0;
                int ite = 0;
                List<int> road = new List<int>();
                road.Add(pos);

                // when it will stop
                while (true)
                {
                    if (road.Count > maxPoi)
                    {
                        break;
                    }

                    // first show the options
                    double[] d = new double[graph.poi[pos].Item3.Count()];
                    int co = 0;
                    foreach (var r in graph.poi[pos].Item3)
                    {
                        if (calculateWeights)
                        {
                            d[co] = graph.poi[r.Item1 - 1].Item2 * 100 / r.Item2;
                        } else
                        d[co] = 1;
                        co++;
                    }
                    double da = 0, ds = 0;
                    double rand = rnd.NextDouble();
                    while (rand == 0.0) rand = rnd.NextDouble();
                    foreach (double de in d)
                    {
                        da += de;
                    }
                    int coi = 0;
                    foreach (double de in d)
                    {
                        ds += de;
                        if (rand <= ds / da)
                        {
                            // this is the step to choose
                            pos = graph.poi[pos].Item3[coi].Item1 - 1;
                            road.Add(pos);
                            ite++;

                            break;
                        }
                        coi++;
                    }
                }

                // keep deleting last points from this road until its functional (from point 1 to 1)
                // save this road if its valid and not too long
                while (road.Count > 2)
                {
                    road ro = new road(road.Count, max);
                    for (int ki = 0; ki < road.Count; ki++)
                    {
                        ro.poi[ki] = road[ki];
                    }
                    ro.map(graph);
                    if (ro.valid && !ro.tooLong)
                    {
                        roads.Add(ro);

                        labelSoFar.Content = (i + 1).ToString();


                        if (allOutput && output)
                        {
                            String text = "Droga " + (i + 1) + " - " + " długość: " + ro.length + ", zysk: " + ro.profit + "\n";
                            foreach (var de in ro.poi)
                            {
                                text += (de + 1) + " ";
                            }
                            debugPopulate.Text += text + "\n";
                        }
                        
                        if (bestSoFar < ro.profit)
                        {
                            if (!allOutput && output)
                            {
                                String text = "Droga " + (i + 1) + " - " + " długość: " + ro.length + ", zysk: " + ro.profit + "\n";
                                foreach (var de in ro.poi)
                                {
                                    text += (de + 1) + " ";
                                }
                                debugPopulate.Text = text + "\n";
                            }
                            

                            bestSoFar = ro.profit;
                            bestSoFarNo = roads.Count - 1;
                            
                        }
                        
                        

                        i++;

                        break;
                    }

                    // it was bad, substract
                    road.RemoveAt(road.Count-1);
                    while (road[road.Count - 1] != 0)
                        road.RemoveAt(road.Count-1);

                }

                if (work)
                if (doThreads)
                    Dispatcher.BeginInvoke(
                        System.Windows.Threading.DispatcherPriority.SystemIdle,
                        new AntsDelegate(this.generateRandom));
                else
                    generateRandom();
                else
                {
                    mrowkowy.IsEnabled = true;
                    randomize.IsEnabled = true;
                }

            }
            else
            {
                mrowkowy.IsEnabled = true;
                randomize.IsEnabled = true;
                stop.IsEnabled = false;
                buttonEvolution.IsEnabled = true;
            }
        }


        private void doAnts()
        {

            if (i < iterations)
            {
                roads = new List<road>();

                // this much ants in every try
                for (int j = 0; j < ants; j++)
                {
                    int pos = 0;
                    int ite = 0;
                    List<int> road = new List<int>();
                    road.Add(pos);

                    // when it will stop
                    while (!(ite != 0 && pos == 0))
                    {
                        if (road.Count > 100)
                        {
                            break;
                        }

                        // first show the options
                        double[] d = new double[graph.poi[pos].Item3.Count()];
                        int co = 0;
                        foreach (var r in graph.poi[pos].Item3)
                        {
                            if (dontVisitAgain && r.Item1 != 0)
                            {
                                // set probability to 0 if already choosen before
                                bool help = false;
                                foreach (var re in road)
                                {
                                    if (re == r.Item1)
                                    {
                                        d[co] = 0;
                                        help = true;
                                        break;
                                    }
                                }
                                if (!help)
                                {
                                    d[co] = Math.Pow(pheromones[pos][co], alfa) * Math.Pow((100 / r.Item2), beta);
                                }
                            }
                            else
                            {
                                d[co] = Math.Pow(pheromones[pos][co], alfa) * Math.Pow((100 / r.Item2), beta);
                            }
                            co++;
                        }
                        double da = 0, ds = 0;
                        double rand = rnd.NextDouble();
                        while (rand == 0.0) rand = rnd.NextDouble();
                        foreach (double de in d)
                        {
                            da += de;
                        }
                        int coi = 0;
                        foreach (double de in d)
                        {
                            ds += de;
                            if (rand <= ds / da)
                            {
                                // this is the step ant choose
                                pos = graph.poi[pos].Item3[coi].Item1 - 1;
                                road.Add(pos);
                                ite++;

                                break;
                            }
                            coi++;
                        }
                    }

                    // save this road if its valid and not too long
                    road ro = new road(road.Count, max);
                    for (int ki = 0; ki < road.Count; ki++)
                    {
                        ro.poi[ki] = road[ki];
                    }
                    ro.map(graph);
                    if (ro.valid && !ro.tooLong)
                    {
                        roads.Add(ro);
                    }


                }



                // now update pheromones for succesful ants
                // first lower all pheromones
                for (int m1 = 0; m1 < graph.poi.Count(); m1++)
                {
                    for (int m2 = 0; m2 < graph.poi[m1].Item3.Count(); m2++)
                    {
                        pheromones[m1][m2] = (1 - lower) * pheromones[m1][m2];
                    }
                }

                // then add to succesful roads
                foreach (road ro in roads)
                {
                    int posi = 0, last = 0;
                    foreach (int mi in ro.poi)
                    {
                        if (posi == 0)
                        {
                            last = mi;
                            posi++;
                            continue;
                        }

                        int mark = 0;
                        foreach (var t in graph.poi[last].Item3)
                        {
                            if (t.Item1 == mi + 1)
                            {
                                break;
                            }
                            mark++;
                        }

                        pheromones[last][mark] += ro.profit;

                        if (biDirectional)
                        {
                            int mark2 = 0;
                            foreach (var t in graph.poi[mi].Item3)
                            {
                                if (t.Item1 == last + 1)
                                {
                                    break;
                                }
                                mark2++;
                            }

                            pheromones[mi][mark2] = pheromones[last][mark];
                        }

                        last = mi;
                        posi++;
                    }

                    //posi++;
                }

                if (debugPopulate.Text.Count() > maxCharacters)
                    debugPopulate.Text = "";


                // show what was done in this iteration
                String text = "Iteracja " + i + ":\n";
                debugPopulate.Text += text;
                int mee = 1;
                foreach (var d in roads)
                {
                    String text2 = "Droga: " + mee + "; długość: " + d.length + "; zysk: " + d.profit + "\n";
                    foreach (var de in d.poi)
                    {
                        text2 += de + 1 + " ";
                    }
                    debugPopulate.Text += text2 + "\n";
                    mee++;
                }

                debugPopulate.Text += "Feromony:" + "\n";

                for (int m1 = 0; m1 < graph.poi.Count(); m1++)
                {
                    debugPopulate.Text += "Punkt " + m1 + 1 + " = ";
                    for (int m2 = 0; m2 < graph.poi[m1].Item3.Count(); m2++)
                    {
                        debugPopulate.Text += graph.poi[m1].Item3[m2].Item1 + "-" + graph.poi[m1].Item3[m2].Item2 + "-" + pheromones[m1][m2] + " ";
                    }
                    debugPopulate.Text += "\n";
                }


                i++;

                if (work)
                if (doThreads)
                    Dispatcher.BeginInvoke(
                        System.Windows.Threading.DispatcherPriority.SystemIdle,
                        new AntsDelegate(this.doAnts));
                else
                    doAnts();
                else
                {
                    mrowkowy.IsEnabled = true;
                    randomize.IsEnabled = true;
                }

            }
            else
            {
                mrowkowy.IsEnabled = true;
                randomize.IsEnabled = true;
                stop.IsEnabled = false;
            }

            

        }

        private void stop_Click(object sender, RoutedEventArgs e)
        {
            work = false;
            stop.IsEnabled = false;
        }


        int curIter = 0;
        int maxIter = 0;
        int turnamentE = 2;

        road bestRoad;

        bool evolutionWork;

        List<road> newRoads;
        List<road> oldRoads;

        // evolution (best, crossover, mutation)
        private void button1_Click(object sender, RoutedEventArgs e)
        {

            if (!int.TryParse(textBox1.Text, out maxIter))
            {
                textBox1.Text = "1000";
                maxIter = 1000;
                
            }
            curIter = 1;
            turnamentE = (int) slider1.Value;


            oldRoads = new List<road>(roads);
            bestRoad = roads.ElementAt(bestSoFarNo);

            debugEvolution.Text += "Najlepszy punkt z wylosowanej populacji:\n";
            debugEvolution.Text += bestRoad.show();

            evolutionWork = true;
            //buttonEvolution.IsEnabled = false;
            buttonEvolutionStop.IsEnabled = true;
            buttonEvolutionStop.Content = "Wstrzymaj";

            if (evolutionWork)
                if (doThreads)
                    Dispatcher.BeginInvoke(
                        System.Windows.Threading.DispatcherPriority.SystemIdle,
                        new EvoDelegate(evolutionDo));
                else
                    evolutionDo();
            else
            {
                buttonEvolution.IsEnabled = true;
            }



        }

        List<road> backupRoads;

        private void evolutionDo()
        {
            if (curIter <= maxIter)
            {
                label5.Content = curIter;

                if (output)
                    debugEvolution.Text += curIter + " iteracja:\n";

                newRoads = new List<road>();

                //debugEvolution.Text += graph.show();

                turnament();

                backupRoads = new List<road>(oldRoads);

                crossover();

                //debugEvolution.Text += "\n" + curIter + " iteracja, przed delete 1:\n";
                //foreach (var ro in oldRoads)
                //    debugEvolution.Text += ro.show();

                mutationDeleteI();

                //debugEvolution.Text += "\n" + curIter + " iteracja, przed delete 2:\n";
                //foreach (var ro in oldRoads)
                //    debugEvolution.Text += ro.show();

                mutationDeleteII();

                //debugEvolution.Text += "\n" + curIter + " iteracja, przed insert:\n";
                //foreach (var ro in oldRoads)
                //    debugEvolution.Text += ro.show();

                mutationInsert();

                //debugEvolution.Text += "\n" + curIter + " iteracja, po wszystkim:\n";
                //foreach (var ro in oldRoads)
                //    debugEvolution.Text += ro.show();

                //debugEvolution.Text += graph.show();

                checkIfValid();


                road best = oldRoads.ElementAt(0);
                foreach (road be in oldRoads)
                {
                    if (be.profit > best.profit)
                        best = be;
                }
                debugEvolution.Text += best.show2();
                

                curIter++;

                if (evolutionWork)
                    if (doThreads)
                        Dispatcher.BeginInvoke(
                            System.Windows.Threading.DispatcherPriority.SystemIdle,
                            new EvoDelegate(evolutionDo));
                    else
                        evolutionDo();
                else
                {
                    //evolutionWork = true;
                }

            }
            else
            {
                evolutionWork = false;
                debugEvolution.Text += "Gotowe!\n";
                buttonEvolutionStop.Content = "Wstrzymaj";
                buttonEvolutionStop.IsEnabled = false;
                //buttonEvolution.IsEnabled = true;
            }

            
        }

        //road backupRoad;

        private void turnament()
        {
            if (output)
                debugEvolution.Text += "Turniej:\n";

            while (newRoads.Count < oldRoads.Count)
            {
                //List<road> tempRoads = new List<road>();
                List<int> tempList = new List<int>();
                int bestProfit = 0;
                int bestNo = 0;
                for (int i = 0; i < turnamentE; i++)
                {
                    double rand = rnd.NextDouble();
                    int el = (int)(rand * (oldRoads.Count - 1));
                    //tempRoads.Add(oldRoads.ElementAt(el));
                    //if (tempList.Exists(o => o.Equals(el)))
                    //{
                    //    i--;
                    //}
                    //else
                    //{
                        tempList.Add(el);
                        if (bestProfit < oldRoads.ElementAt(el).profit)
                        {
                            bestProfit = oldRoads.ElementAt(el).profit;
                            bestNo = el;
                        }
                    //}
                }
                newRoads.Add(oldRoads.ElementAt(bestNo));
                if (output)
                    debugEvolution.Text += oldRoads.ElementAt(bestNo).show();
            }

            if (output)
                debugEvolution.Text += "Turniej zakończony\n";

        }

        private void crossover()
        {
            // we have input in newRoad, but output in oldRoad for this one
            oldRoads = new List<road>();

            while (newRoads.Count > 1)
            {
                // delete roads from one end and add to the other
                double rand = rnd.NextDouble();
                int el = (int)(rand * (newRoads.Count - 1));
                road tmpRoad = newRoads.ElementAt(el);
                newRoads.RemoveAt(el);

                double rand2 = rnd.NextDouble();
                int el2 = (int)(rand * (newRoads.Count - 1));
                road tmpRoad2 = newRoads.ElementAt(el);
                newRoads.RemoveAt(el2);

                if (output)
                    debugEvolution.Text += "Rodzice:\n" + tmpRoad.show() + tmpRoad2.show();

                if (tmpRoad.poi.Count() > 3 && tmpRoad2.poi.Count() > 3)
                {
                    bool exitLoop = false;
                    for (int ien = 1; ien < tmpRoad.poi.Count() - 1; ien++)
                    {
                        for (int iem = 1; iem < tmpRoad2.poi.Count() - 1; iem++)
                        {
                            if (tmpRoad.poi[ien].Equals(tmpRoad2.poi[iem]))
                            {
                                int length = ien + tmpRoad2.poi.Count() - iem;
                                int length2 = iem + tmpRoad.poi.Count() - ien;
                                road newRo = new road(length, max);
                                road newRo2 = new road(length2, max);
                                int helper = 0;
                                for (int ieb = 0; ieb < length; ieb++)
                                {
                                    if (ieb < ien)
                                    {
                                        newRo.poi[ieb] = tmpRoad.poi[ieb];
                                    }
                                    else
                                    {
                                        newRo.poi[ieb] = tmpRoad2.poi[iem + helper];
                                        helper++;
                                    }
                                }
                                helper = 0;
                                for (int ieb = 0; ieb < length2; ieb++)
                                {
                                    if (ieb < iem)
                                    {
                                        newRo2.poi[ieb] = tmpRoad2.poi[ieb];
                                    }
                                    else
                                    {
                                        newRo2.poi[ieb] = tmpRoad.poi[ien + helper];
                                        helper++;
                                    }
                                }

                                newRo.map(graph);
                                newRo2.map(graph);
                                oldRoads.Add(newRo);
                                oldRoads.Add(newRo2);

                                if (output)
                                    debugEvolution.Text += "Skrzyżowane punkty:\n" + newRo.show() + newRo2.show();

                                exitLoop = true;
                            }
                            if (exitLoop)
                                break;
                        }
                        if (exitLoop)
                            break;
                    }
                    if (!exitLoop)
                    {
                        oldRoads.Add(tmpRoad);
                        oldRoads.Add(tmpRoad2);
                    }
                }
                else
                {
                    oldRoads.Add(tmpRoad);
                    oldRoads.Add(tmpRoad2);
                }
                
            }
            if (newRoads.Count > 0)
            {
                oldRoads.Add(newRoads.ElementAt(0));
                newRoads.RemoveAt(0);
            }
        }

        private void mutationDeleteI() 
        {
            for (int iem = 0; iem < oldRoads.Count; iem++)
            {
                road ro = oldRoads.ElementAt(iem);

                //debugEvolution.Text += "\n" + curIter + " iteracja, we work on:\n";
                //debugEvolution.Text += ro.show();

                for (int ien = 1; ien < ro.getPoints() - 1; ien++)
                {
                    //debugEvolution.Text += "iteracja " + ien + "\n";

                    if (ro.poi[ien] == 0)
                    {

                        //debugEvolution.Text += "W iteracji " + ien + " znaleziono 1, we try to delete...\n";

                        // we try to delete it
                        if (ro.canDelete(ien, graph))
                        {
                            //debugEvolution.Text += "Mozemy kasowac!:\n";

                            road ra = deletePoint(ro, ien);
                            oldRoads.RemoveAt(iem);
                            oldRoads.Insert(iem, ra);
                            ro = ra;
                            ien--;

                            //debugEvolution.Text += "nowy obiekt:\n";
                            //debugEvolution.Text += ro.show();
                        }
                    }
                    // but if its not starting/ending point, check if it is there multiple times
                    else
                    {
                        if (ro.canDelete(ien, graph))
                        for (int ieb = 1; ieb < ro.getPoints() - 1; ieb++)
                        {
                            if (ieb != ien && ro.poi[ieb] == ro.poi[ien])
                            {
                                //debugEvolution.Text += "W iteracji " + ien + " w poditeracji " + ieb + " znaleziono duplikat, sprawdzam czy moge skasowac ien...\n";
                                // we try to delete it
                                //if (ro.canDelete(ien, graph))
                                {
                                    //debugEvolution.Text += "Mozemy kasowac!:\n";

                                    road ra = deletePoint(ro, ien);
                                    oldRoads.RemoveAt(iem);
                                    oldRoads.Insert(iem, ra);
                                    ro = ra;
                                    ien--;

                                    //debugEvolution.Text += "nowy obiekt:\n";
                                    //debugEvolution.Text += ro.show();
                                }
                                break;
                            }
                        }
                    }

                }

            }
        }

        private void mutationDeleteII()
        {
            //foreach (road ro in oldRoads)
            for (int iem = 0; iem < oldRoads.Count; iem ++)
            {
                road ro = oldRoads.ElementAt(iem);
                double rand = rnd.NextDouble();
                int el = (int)(rand * (ro.poi.Count() - 3)) + 1;
                if (ro.canDelete(el, graph))
                {
                    road ra = deletePoint(ro, el);

                    oldRoads.RemoveAt(iem);
                    oldRoads.Insert(iem, ra);

                }
            }
        }

        private road deletePoint(road ro, int el)
        {
            road ra = new road(ro.getPoints() - 1, ro.getMax());

            for (int ien = 0; ien < ra.getPoints(); ien++)
            {
                if (ien < el)
                    ra.poi[ien] = ro.poi[ien];
                else
                    ra.poi[ien] = ro.poi[ien + 1];
            }
            ra.map(graph);

            return ra;
        }

        private void mutationInsert()
        {
            for (int iem = 0; iem < oldRoads.Count; iem++)
            {
                road ro = oldRoads.ElementAt(iem);
                if (!ro.tooLong)
                {
                    double rand = rnd.NextDouble();
                    int el = (int)(rand * (ro.poi.Count() - 2));
                    //List<int> cities = new List<int>();
                    List<Tuple<int, int>> cities = new List<Tuple<int,int>>();
                    int maxProfit = 0;
                    for (int ien = 0; ien < graph.poi[ro.poi[el]].Item3.Count(); ien++)
                    {
                        int meh = graph.poi[ro.poi[el]].Item3[ien].Item1;
                        if (!ro.cityExists(meh - 1))
                        {
                            // there is a way to this unvisited city
                            // check if there is a way from that city to our next city on the list
                            for (int ieb = 0; ieb < graph.poi[meh - 1].Item3.Count(); ieb++)
                            {
                                if (graph.poi[meh - 1].Item3[ieb].Item1 == ro.poi[el + 1] + 1)
                                {
                                    // there IS a way back on track
                                    // check if adding it won't make it too big
                                    if (ro.length + graph.poi[meh - 1].Item2 < ro.getMax())
                                    {
                                        // it won't, now add it on the list
                                        cities.Add(new Tuple<int, int>(meh - 1, ien));

                                        // also keep record of longest one, so we can delete all shorter
                                        if (maxProfit < graph.poi[meh - 1].Item2)
                                            maxProfit = graph.poi[meh - 1].Item2;
                                    }
                                    // we already found the path
                                    break;
                                }
                            }
                        }
                    }

                    if (cities.Count > 0)
                    {

                        // delete shorter than optimal
                        int iev = 0;
                        while (iev < cities.Count)
                        {
                            if (graph.poi[cities[iev].Item1].Item2 < maxProfit)
                            {
                                cities.RemoveAt(iev);
                            }
                            else
                            {
                                iev++;
                            }
                        }
                        // choose lowest road cost
                        int lowest = 0;
                        iev = 0;
                        while (iev < cities.Count)
                        {
                            //if (graph.poi[iem].Item3[cities[iev].Item2-1].Item2 < graph.poi[iem].Item3[cities[lowest].Item2-1].Item2)
                            if (graph.poi[ro.poi[el]].Item3[cities[iev].Item2].Item2 < graph.poi[ro.poi[el]].Item3[cities[lowest].Item2].Item2)
                            {
                                lowest = iev;
                            }

                            iev++;
                        }
                        //proceed to add that one to the chain
                        road ra = new road(ro.getPoints() + 1, ro.getMax());

                        for (int ien = 0; ien < ra.getPoints(); ien++)
                        {
                            if (ien <= el)
                                ra.poi[ien] = ro.poi[ien];
                            else if (ien == el + 1)
                                ra.poi[ien] = cities[lowest].Item1;
                            else
                                ra.poi[ien] = ro.poi[ien - 1];
                        }
                        ra.map(graph);

                        oldRoads.RemoveAt(iem);
                        oldRoads.Insert(iem, ra);

                    }
                    


                }
            }
        }

        private void checkIfValid()
        {
            for (int iem = 0; iem < oldRoads.Count; iem++)
            {
                if (oldRoads.ElementAt(iem).tooLong || !oldRoads.ElementAt(iem).valid)
                {
                    double rand = rnd.NextDouble();
                    int el = (int)(rand * (backupRoads.Count - 1));
                    road newR = backupRoads.ElementAt(el);
                    while (!newR.valid || newR.tooLong)
                    {
                        rand = rnd.NextDouble();
                        el = (int)(rand * (backupRoads.Count - 1));
                        newR = backupRoads.ElementAt(el);
                    }
                    oldRoads.RemoveAt(iem);
                    oldRoads.Insert(iem, newR);
                }
            }
        }

        private void buttonEvolutionStop_Click(object sender, RoutedEventArgs e)
        {
            if (evolutionWork)
            {
                evolutionWork = false;
                buttonEvolutionStop.Content = "Kontynuuj";
            }
            else
            {
                evolutionWork = true;
                buttonEvolutionStop.Content = "Wstrzymaj";

                if (doThreads)
                    Dispatcher.BeginInvoke(
                        System.Windows.Threading.DispatcherPriority.SystemIdle,
                        new EvoDelegate(evolutionDo));
                else
                    evolutionDo();
            }
        }

        private void slider1_ValueChanged(object sender, RoutedPropertyChangedEventArgs<double> e)
        {
            textBoxTurniej.Text = slider1.Value.ToString();
        }

        private void textBoxTurniej_TextChanged(object sender, TextChangedEventArgs e)
        {
            int meh = 1;
            if (int.TryParse(textBoxTurniej.Text, out meh) && slider1 != null)
            {
                //if (meh <= slider1.Maximum && meh >= slider1.Maximum)
                    slider1.Value = meh;
                //textBoxTurniej.Text = slider1.Value.ToString();
            }



        }

        private void button1_Click_1(object sender, RoutedEventArgs e)
        {
            debugEvolution.Text = "";
        }

        private void checkBoxOutput_Checked(object sender, RoutedEventArgs e)
        {
            output = true;
            if (checkBoxOutput != null)
                checkBoxOutput.IsChecked = true;
            if (checkBoxShowOut != null)
                checkBoxShowOut.IsChecked = true;
        }

        private void checkBoxOutput_Unchecked(object sender, RoutedEventArgs e)
        {
            output = false;
            if (checkBoxOutput != null)
                checkBoxOutput.IsChecked = false;
            if (checkBoxShowOut != null)
                checkBoxShowOut.IsChecked = false;
        }




        





        // END OF CLASS
    }
}
